\section{Introduction}
In a dynamic network, nodes (processors/end hosts) and communication
links can appear and disappear at will over time.  Emerging networking
technologies such as ad hoc wireless, sensor, and mobile networks,
overlay and peer-to-peer (P2P) networks are inherently dynamic,
resource-constrained, and unreliable.  This necessitates the
development of a solid theoretical foundation to design efficient,
robust, and scalable distributed algorithms and to understand the
power and limitations of distributed computing on such networks.  Such
a foundation is critical to realize the full potential of these
large-scale dynamic communication networks.

As a step towards understanding the fundamental computation power of
dynamic networks, we investigate dynamic networks in which the network
topology changes arbitrarily from round to round.  We first consider a
worst-case model that was introduced by Kuhn, Lynch, and
Oshman~\cite{kuhn+lo:dynamic} in which the communication links for
each round are chosen by an online adversary, and nodes do not know
who their neighbors for the current round are before they broadcast
their messages. (Note that in this model, only edges change and nodes
are assumed to be fixed.)  The only constraint on the adversary is
that the network should be connected at each round.  Unlike prior
models on dynamic networks, the model of~\cite{kuhn+lo:dynamic} does
not assume that the network eventually stops changing and requires
that the algorithms work correctly and terminate even in networks that
change continually over time.

In this paper, we study the fundamental problem of information
spreading (also known as gossip).  In gossip, or more generally,
$k$-gossip, there are $k$ pieces of information (or tokens) that are
initially present in some nodes and the problem is to disseminate the
$k$ tokens to all nodes.  (By just gossip, we mean $n$-gossip, where
$n$ is the network size.)  Information spreading is a fundamental
primitive in networks which can be used to solve other problem such as
broadcasting and leader election. Indeed, solving $n$-gossip, where
the number of tokens is equal to the number of nodes in the network,
and each node starts with exactly one token, allows any function of
the initial states of the nodes to be computed, assuming that the
nodes know $n$~\cite{kuhn+lo:dynamic}.  

\subsection{Our results}
The focus of this paper is on the power of {\em token-forwarding}\/
algorithms, which do not manipulate tokens in any way other than
storing and forwarding them.  Token-forwarding algorithms are simple,
often easy to implement, and typically incur low overhead.  In a key
result,~\cite{kuhn+lo:dynamic} showed that under their adversarial
model, $k$-gossip can be solved by token-forwarding in $O(nk)$ rounds,
but that any deterministic online token-forwarding algorithm needs
$\Omega(n \log k)$ rounds.  They also proved an $\Omega(nk)$ lower
bound for a special class of token-forwarding algorithms, called
knowledge-based algorithms.  Our main result is a new lower bound that
applies to {\em any}\/ deterministic online token-forwarding algorithm
for $k$-gossip.
\begin{itemize}
\item
We show that every online algorithm for the $k$-gossip problem takes
$\Omega(nk/\log n)$ rounds against an adversary that, at the start of
each round, knows the randomness used by the algorithm in the round.
This also implies that any deterministic online token-forwarding
algorithm takes $\Omega(nk/\log n)$ rounds.  Our result applies even
to centralized token-forwarding algorithms that have a global
knowledge of the token distribution.
\end{itemize}
This result resolves an open problem raised in~\cite{kuhn+lo:dynamic},
significantly improving their lower bound, and matching their upper
bound to within a logarithmic factor.  Our lower bound also enables a
better comparison of token-forwarding with an alternative approach
based on network coding due to
~\cite{haeupler:gossip,haeupler+k:dynamic}, which achieves a
$O(nk/\log n)$ rounds using $O(\log n)$-bit messages (which is not
significantly better than the $O(nk)$ bound using token-forwarding),
and $O(n + k)$ rounds with large message sizes (e.g., $\Theta(n \log
n)$ bits).  It thus follows that for large token and message sizes
there is a factor $\Omega(\min\{n,k\}/\log n)$ gap between
token-forwarding and network coding. We note that in our model we
allow only one token per edge per round and thus our bounds hold
regardless of the token size.

Our lower bound indicates that one cannot obtain efficient (i.e.,
subquadratic) token-forwarding algorithms for gossip in the
adversarial model of~\cite{kuhn+lo:dynamic}.  Furthermore, for
arbitrary token sizes, we do not know of any algorithm that is
significantly faster than quadratic time.  This motivates considering
other weaker (and perhaps, more realistic) models of dynamic networks.
In fact, it is not clear whether one can solve the problem
significantly faster even in an offline setting, in which the network
can change arbitrarily each round, but the entire evolution is known
to the algorithm in advance.  Our next contribution takes a step in
resolving this basic question for token-forwarding algorithms.
\begin{itemize}
\item
We present a polynomial-time offline token-forwarding algorithm that
solves the $k$-gossip problem on an $n$-node dynamic network in
$O(\min\{nk, n \sqrt{k \log n}\})$ rounds with high probability.
\item
We also present a polynomial-time offline token-forwarding algorithm
that solves the $k$-gossip problem in a number of rounds within an
$O(n^\eps)$ factor of the optimal, for any $\eps > 0$, assuming the
algorithm is allowed to transmit $O(\log n)$ tokens per round.
\end{itemize}
The above upper bounds show that in the offline setting,
token-forwarding algorithms can achieve a time bound that is within
$O(\sqrt{k\log n})$ of the information-theoretic lower bound of
$\Omega(n + k)$, and that we can approximate the best token-forwarding
algorithm to within a $O(n^\eps)$ factor, given logarithmic extra
bandwidth per edge.

\subsection{Related work}
Information spreading (or dissemination) in networks is one of the
most basic problems in computing and has a rich literature. \junk{Here
  we focus mostly on work that is relevant to our work.} The problem
is generally well-understood on static networks, both for
interconnection networks~\cite{leighton:book} as well as general
networks~\cite{lynch:distributed,attiya+w:distributed}.  In
particular, the $k$-gossip problem can be solved in $O(n + k)$ rounds
on any $n$-static network~\cite{topkis:disseminate}.  There also have
been several papers on broadcasting, multicasting, and related
problems in static heterogeneous and wireless networks (e.g.,
see~\cite{alon+blp:radio,bar-yehuda+gi:radio,bar-noy+gns:multicast,clementi+ms:radio}).

Dynamic networks have been studied extensively over the past three
decades.  Some of the early studies focused on dynamics that arise out
of faults, i.e., when edges or nodes fail.  A number of fault models,
varying according to extent and nature (e.g., probabilistic
vs.\ worst-case) and the resulting dynamic networks have been analyzed
(e.g., see~\cite{attiya+w:distributed,lynch:distributed}).  There have
been several studies on models that constrain the rate at which
changes occur, or assume that the network eventually stabilizes (e.g.,
see~\cite{afek+ag:dynamic,dolev:stabilize,gafni+b:link-reversal}).

There also has been considerable work on general dynamic networks.
Some of the earliest studies in this area
include~\cite{afek+gr:slide,awerbuch+pps:dynamic} which introduce
general building blocks for communication protocols on dynamic
networks.  \junk{Subsequently, a number of different problems have
  been studied on dynamic and asynchronous networks, including
  routing, load balancing, multicast, anycast, and several fundamental
  distributed computing problems.}  Another notable work is the local
balancing approach of~\cite{awerbuch+l:flow} for solving routing and
multicommodity flow problems on dynamic networks.  Algorithms based on
the local balancing approach continually balance the packet queues
across each edge of the network and drain packets that have reached
their destination.  \junk{It has been shown that assuming the queues
  at the nodes can hold enough packets, the local balancing approach
  can achieve throughput that is arbitrarily close to the optimal
  achievable by any offline algorithm.}  The local balancing approach
has been applied to achieve near-optimal throughput for multicast,
anycast, and broadcast problems on dynamic networks as well as for
mobile ad hoc
networks~\cite{awerbuch+bbs:route,awerbuch+bs:anycast,jia+rs:adhoc}.

Modeling general dynamic networks has gained renewed attention with
the recent advent of heterogeneous networks composed out of ad hoc,
and mobile devices.  To address the unpredictable and often unknown
nature of network dynamics,~\cite{kuhn+lo:dynamic} introduce a model
in which the communication graph can change completely from one round
to another, with the only constraint being that the network is
connected at each round.  The model of~\cite{kuhn+lo:dynamic} allows
for a much stronger adversary than the ones considered in past work on
general dynamic
networks~\cite{awerbuch+l:flow,awerbuch+bbs:route,awerbuch+bs:anycast}.
In addition to results on the $k$-gossip problem that we have
discussed earlier,~\cite{kuhn+lo:dynamic} consider the related problem
of counting, and generalize their results to the $T$-interval
connectivity model, which includes an additional constraint that any
interval of $T$ rounds has a stable connected spanning subgraph.  The
survey of~\cite{kuhn-survey} summarizes recent work on dynamic
networks.
 
We note that the model of~\cite{kuhn+lo:dynamic}, as well as ours,
allow only edge changes from round to round while the nodes remain
fixed. Recently, the work of \cite{p2p-soda} introduced a dynamic
network model (motivated by P2P networks) where both nodes and edges
can change by a large amount (up to a linear fraction of the network
size). They show that stable almost-everywhere agreement can be
efficiently solved in such networks even in adversarial dynamic
settings.  \junk{As in the Kuhn et al. model, the algorithms in
  \cite{p2p-soda} will work and terminate correctly even when the
  network keeps continually changing.  We note that there has been
considerable prior work in dynamic P2P networks (see \cite{p2p-soda,
  p2p-focs} and the references therein) but these don't assume that
the network keeps continually changing over time.}

Recent work of~\cite{haeupler:gossip,haeupler+k:dynamic} presents
information spreading algorithms based on network
coding~\cite{ahlswede+cly:coding}.  As mentioned earlier, one of their
important results is that the $k$-gossip problem on the adversarial
model of~\cite{kuhn+lo:dynamic} can be solved using network coding in
$O(n+k)$ rounds assuming the token sizes are sufficiently large
($\Omega(n\log n)$ bits). For further references to using network
coding for gossip and related problems, we refer to the recent works
of
~\cite{haeupler:gossip,haeupler+k:dynamic,avin1,avin2,deb+mc:coding,shah}
and the references therein.

Our offline approximation algorithm makes use of results on the
Steiner tree packing problem for directed
graphs~\cite{cheriyan+s:steiner}.  This problem is closely related to
the directed Steiner tree problem (a major open problem in
approximation
algorithms)~\cite{charikar+ccdgg:steiner,zosin+k:steiner} and the gap
between network coding and flow-based solutions for multicast in
arbitrary directed networks~\cite{agarwal+c:coding,sanders+et:flow}.

Finally, we note that there are also a number of studies that solve
$k$-gossip and related problems using {\em gossip-based}\/ processes.
In a local gossip-based algorithm, each node exchanges information
with a small number of randomly chosen neighbors in each round.
Gossip-based processes have recently received significant attention
because of their simplicity of implementation, scalability to large
network size, and their use in aggregate computations,
e.g.,~\cite{berenbrink+ceg:gossip,demers,kempe1,chen-spaa,karp,shah,boyd}
and the references therein.  All these studies assume an underlying
static communication network, and do not apply directly to the models
considered in this paper.  A related recent work on dynamic networks
is~\cite{avin+kl:dynamic} which analyzes the cover time of random
walks on dynamic networks. 


